1. Technical Field
This invention relates to updating content stored in a storage memory device. More specifically, this invention relates to in-place updating an original version of content in a non-volatile storage to an updated version.
2. Discussion of Related Art
It is sometimes required to update content stored in a storage device. For example, if the content is a program (such as an executable file), it is sometimes required to fix a bug existing therein or introduce new features thereto. Yet, the latter example is non-limiting and other types of content may also require updates, such as text, data stored in a database, etc. The terms “old version” or “original version” refer to a version of content before update, and the terms “new version” or “updated version” refer to a version that includes already updated content. In other words, an original (or old) version includes “original (or old) content” while an updated (or new) version includes “updated (or new) content”. It should be noted that updated content can be further updated. In case of a second update, for example, the updated content of the first update turns to be original content of the second update while new updated content is generated by the second update etc.
A process during which original content is updated, yielding updated content is referred to as an “update process”. The update process usually requires instructions on how to perform the update. Such instructions constitute together an “update package”, wherein each instruction included therein constitutes an “update command”. That is, an update package is obtained as input, and during the update process original content is updated to updated content in accordance therewith. This is non-limiting though and sometimes more than one update package can be obtained which together allow the updating of content. Alternatively, instead of an update package being obtained, an update package (or a set of update commands) may be retrieved from a storage or from a database etc. Hence, hereinafter, when referring to the term “obtaining an update package” it should be appreciated that the update package can be passively obtained or actively retrieved, or sometimes an embedded package (e.g., a hard coded set of update commands) can be activated.
One way to update an original version to an updated version is storing the updated version in the storage in addition to the original version. For example, a computer program “prog.exe” is activated whenever a user presses a certain icon on the PC (Personal Computer) windows desktop. In order to update prog.exe it is possible to store the updated version of this file in a different location than the present (original) version, and then reset the path associated with the icon so as to activate the updated version instead of the original version. Later, when it is ascertained that the update process completed successfully, the original version can be deleted safely, releasing the space occupied thereby. In addition to increasing storage consumption, this latter update method requires that the complete updated version be provided to the update process, e.g., in the update package.
One way for reducing the size of an update package is by including in it information representing the differences between the original and updated content. Such an update package is sometimes referred to also as a “difference”, a “difference result” or a “delta”. The update process, upon operating in accordance with a delta, applies it to the original content, hence producing the updated content. Deltas may be produced using the known in the art differencing algorithms (such as “GNU diff”) in a naïve manner, though such deltas tend to be rather large.
The size of the delta being considered, there are methods trying to reduce the size thereof. For example, U.S. Pat. No. 6,546,552 (“Difference extraction between two versions of data-tables containing intra-references”, published 2003) discloses a method for generating a compact difference result between an old program and a new program. Each program includes reference entries that contain references that refer to other entries in the program. According to the method of U.S. Pat. No. 6,546,552, the old program is scanned and for each reference entry, the reference is replaced by a distinct label mark, whereby a modified old program is generated. In addition, according to U.S. Pat. No. 6,546,552, the new program is scanned and for each reference entry the reference is replaced by a distinct label mark, whereby a modified new program is generated. Thus, utilizing directly or indirectly the modified old program and modified new program, the difference result is generated.
WO 2004/114130 (“Method and system for updating versions of content stored in a storage device”, published 2004) discloses another system and method for generating a compact update package between an old version of content and a new version of content. The system of WO 2004/114130 includes a conversion element generator for generating a conversion element associated with the old version and new version. It also includes a modified version generator for generating a modified version, and an update package generator for generating the compact update package. The compact update package includes the conversion element and a modified delta based on the modified version and the new version.
WO 2005/003963 (“Method and system for updating versions of content stored in a storage device”, published 2005) discloses a system and method for updating versions of content stored in a storage. The system of WO 2005/003963 includes an update module for obtaining a conversion element and a small delta. It also includes a converted old items generator for generating converted old items by applying the conversion element to items of an old version, a data entries generator for generating data entries based on the modified data entries and on the converted old item, and a new version generator for generating a new version of content by applying the commands and the data entries to the old version.
It was noted before that a certain type of update package is sometimes referred to as a delta, however, this is non-limiting, and as it appears from WO 2004/114130 and WO 2005/003963, an update package may sometimes include a delta therewith, or as another example the update package may include the entire updated version.
Other methods exist in the art which take care of additional considerations involved in the update. Prior to elaborating on other methods these considerations should be pointed out.
It is appreciated that content is normally stored in a storage. A storage can include volatile memory, i.e. volatile storage (such as Random Access Memory RAM, etc.) and/or non-volatile memory, i.e. non-volatile storage (such as a hard disk, flash memory, EPROM (Erasable Programmable Read-Only Memory) and/or EEPROM (Electrically EPROM), etc).
There are storages that are organized in discrete areas, referred to, e.g., as blocks or sectors, wherein one block can include content belonging to more than one file. Hence, if there are, for example, two files stored in a storage, a single block can include several (‘x’) bytes belonging to a first of the two files, as well as several (‘y’) bytes belonging to a second of the two files. If the size of a block is ‘z’ bytes, it is clear that z>=x+y. Yet, those versed in the art would appreciate that writing content into a block affects other content stored therein. That is, if it is required to re-write the content stored in the x bytes of the first file (e.g., during update thereof), due to storage limitations it may be impossible to write only those x bytes, and it may be necessary to write the content of all the z bytes to the storage. This can be done, for example, by reading content stored in the z bytes from the non-volatile storage to a volatile storage not including blocks, such as RAM, updating only the content stored in the x bytes in the volatile storage (that is, the content of the other z-x bytes is left unaffected therein) and then writing the content of the z bytes back to the non-volatile storage. This limitation characterizes flash memory, for example, wherein it is required to completely delete the present content of a block, before new content (including updated content) can be written thereto, and hard disks where it is not obligatory to delete the complete sector before writing data thereto, but it is required to write the complete content of a block in one writing operation (e.g., it is impossible to write only x bytes when leaving the content stored in the z-x bytes unaffected. In order to leave the z-x bytes unaffected, it is required to store the content thereof in the volatile memory and write them back into the block, together with the x bytes). Hence, the update procedure may require many write operations to the storage including blocks, and it is appreciated that if it is desirable to achieve an efficient update, the update should better be optimized. For example, if x equals, for example, two bytes, than these two bytes should better be updated together, instead of updating the first byte and then the second byte, writing these two bytes separately into the block.
Furthermore, when in-place updating an original version (including original content) to an updated version (including updated content), there are sometimes update commands that use original content in order to generate updated content. For example, it is possible to copy original content from one place to a different place in the storage, wherein this copied content, in its destination place, forms part of the updated version. When copying content to a destination place it should be appreciated that this destination place could have been used before for storing other content (possibly also being part of the original version). Hence, the copied content can overwrite the original content at the destination place. Still further, it is possible that there is another update command that uses the destination place's original content in order to generate updated content. If this other update command is called further to operating in accordance with the first copy command, the destination place's original content can be already overwritten. This situation constitutes a “write before read conflict”. Herein below unless otherwise noted the term “conflict” is used for short for “write before read conflict”.
Write before read conflicts are a known problem in the art and U.S. Pat. No. 6,018,747 tries to cope therewith.
U.S. Pat. No. 6,018,747 (“Method for generating and reconstructing in-place delta files”, published 2000) discloses a method, apparatus, and article of manufacture for generating, transmitting, replicating, and rebuilding in-place reconstruct software updates to a file from a source computer to a target computer. U.S. Pat. No. 6,018,747 stores the first version of the file and the updates to the first version of the file in the memory of the source computer. The first version is also stored in the memory of the target computer. The updates are then transmitted from the memory of the source computer to the memory of the target computer. These updates are used at the target computer to build the second version of the file in-place.
According to U.S. Pat. No. 6,018,747, when a delta file attempts to read from a memory offset that has already been overwritten, this will result in an incorrect reconstruction since the prior version data has been overwritten. This is termed a write before read conflict. U.S. Pat. No. 6,018,747 teaches how to post-process a delta file in order to create a delta file, minimize the number of write before read conflicts, and then replace copy commands with add commands to eliminate conflicts, thus converting a delta file to an equivalent but larger delta file. A digraph is generated, for representing the write before read conflicts between copy commands. A schedule is generated that eliminates write before read conflicts by converting this digraph into an acyclic digraph.
Another known problem in the art is reliability of the update process, or fail safe update. This problem occurs, for example, when a process of updating an original version is interrupted before its normal termination, such as in a power failure. In such a case, there is a possibility that the content of the block which was being updated during the interruption may become corrupted and contain unexpected content.
It was already mentioned before that when in-place updating blocks of content, an original content of a block sometimes forms part of the input used by the update process. In such a case, if the original block (which is corrupted due to interruption) is required, the update process may be unable to resume. It can be impossible to re-update the corrupted block.
U.S. Pat. No. 6,832,373 (“System and method for updating and distributing information”, published 2004), for example, tries to provide a fail safe update. It discloses devices, systems and methods for updating digital information sequences that are comprised by software, devices, and data. In addition, these digital information sequences may be stored and used in various forms, including, but not limited to files, memory locations, and/or embedded storage locations. Furthermore, the devices, systems, and methods described in U.S. Pat. No. 6,832,373 provide a developer skilled in the art with an ability to generate update information as needed and, additionally, allow users to proceed through a simplified update path, which is not error-prone, and according to U.S. Pat. No. 6,832,373's inventors, may be performed more quickly than through the use of technologies existing when U.S. Pat. No. 6,832,373 was filed.
That is, U.S. Pat. No. 6,832,373 describes using an auxiliary backup block, while all block update operations are performed thereby using two phases ‘two-phase protocol’ or ‘two-phase commit’. According to U.S. Pat. No. 6,832,373, in a first phase of updating a block, the update process writes the updated content to the auxiliary backup block and verifies that the content is correctly stored. In a second phase, the update process writes the updated content into its target block to form the updated content of the updated target block (thereby overwriting the original content of the target block). Yet, variations of the same method exist, such as copying the original content of the target block into the auxiliary backup block in the first phase, and in the second phase in-place updating the target block to store the updated content.
The two phase commit (whether the backed up content is the original content or the updated content) can use only one additional backup block, yet, it is time consuming, since every write operation requires performing two operations (for the two phases). In addition, according to U.S. Pat. No. 6,832,373 every backup operation backs up the complete (original or updated) content of a block in the auxiliary backup block, and hence if the number of blocks whose content is updated by the update process is n, the total number of operations required for the update process (including update operations and write operations into the auxiliary backup block) cannot be smaller than 2n. If there are blocks in which content is stored in more than one write operation, the number of operations that the update process is required to perform will be even larger than 2n.
WO 2007/023497 (“Method and system for in-place updating content stored in a storage device”, published 2007) discloses a system and method for reliable in-place update, performing m block storage operations, including write operations and backup operations, wherein 2<=m<2n. WO 2007/023497 protects before updating all the original content requiring protection, using a protection buffer (also known as a backup buffer) and the delta file. Thus, WO 2007/023497 resolves write before read conflicts as well as maintaining reliable update.
During an update process some or all of the stored original content of the updatable device is updated. The term “updatable device” or “device” refers to any device that is associated with a storage and which allows updating content stored therein. Typically, the stored original content of the updatable device includes software for normal mode process(es), that is for process(es) unrelated to the updating of the content (called here software for the core). Additionally, the stored original content includes software for the update process which is executed during the update mode, that is software related to updating the stored original content (called here software for the “miniOS”, mini-operating system). During the update process, some or all of the stored software for the core and/or for the miniOS is updated. It is noted however that there are certain task(s) which is/are neither exclusive to the update process nor to the other unrelated process(es), and therefore may potentially be required both during the update process and during other unrelated process(es) performed by the updatable device. Such task(s) may include for example non-volatile memory read/write, basic user interface such as keyboard functions, etc. Since the core software is subject to updates, in order for an update task to be executable both by the core and the miniOS, the software procedure defining the update-task must be duplicated and stored twice, both as part of the software for the core and as part of the software for the miniOS, being capable of re-writing the core in-place during the update process. In some cases, each storage of the (duplicated) procedure(s) which may potentially be required both during the update process and during other process(es) necessitates about 5 Megabytes. It is noted that the miniOS also performs tasks unique to the update process (and which are typically not executed by the core), and therefore the miniOS also includes modules such as an update agent (UA) and update installer (UPI) which typically operate only during the update process. However, in some cases the software for the UA and UPI together have a size of between 200 and 400 Kbytes, and therefore the duplicated procedure(s) comprised in the miniOS typically take(s) up a more substantial part of storage than the UA and UPI.
Refer to FIG. 1 which shows a simplified layout of a non-volatile memory 110 comprised in a storage associated with an updatable device. As illustrated in FIG. 1, non-volatile memory 110 includes a section 112 for storing software for a boot loader, a “critical” section 116 for storing software for the miniOS, a backup section 114 for storing a backup of software for the miniOS, a section 118 for storing the software for the non-paged part of the core, a section 120 for storing the software for the paged part of the core, a file system section 122 for storing inter-alia an update package, and a section with one or more backup buffer(s) 124 for storing a normal mode/update mode flag and possibly other data. The stored software for the miniOS includes: software for the UA, software for the UPI, non-volatile memory read/write drivers, and any other “duplicated” procedure(s) for tasks that may potentially be required both during the update process and during other unrelated process(es).
In operation, when an updatable device is reset, the boot loader checks a normal/update flag in a designated backup buffer 124. As mentioned above, in this configuration the update process is performed only during the update mode, and any process which is unrelated to the update process is performed during normal mode. It is noted that in this configuration the boot loader is kept minimal with the boot loader capable of writing to volatile memory but not to non-volatile memory 110 and with the boot loader incapable of even accessing file system 122. If the flag indicates “normal” mode, the boot loader loads the software for the non-paged core to volatile memory. The non-paged core then starts the normal mode of operation of the updatable device as is known in the art.
If instead the flag indicates update mode, the boot loader loads the (original) software for the miniOS to volatile memory. Subsequently the boot loader invokes the original UA (whose software, being part of the miniOS software, is now in volatile memory). The UA then obtains an update package from the location where the update package was previously stored by a device management application. The update package relates to updating some or all of the software for the non-paged core and/or paged core, and optionally relates to updating some or all of the software for the miniOS (It should be understood therefore that an updated version of software may in some cases include some identical content as in the original version.) The UA then stores the obtained update package in file system 122.
If update of the miniOS software is required, the UA invokes the UPI (whose software, being part of the miniOS software, is now in volatile memory) to update the software of the miniOS, and the UA stores a backup of the updated miniOS software in backup 114. It is noted that for reliability purposes critical section 116 is not updated in-place. Rather, the updated software for the miniOS is written to backup 114 and not immediately to critical section 116 so that if during the writing there is an interruption which erases the volatile memory, the update may be reliably resumed with the original version of the software for the miniOS still stored in critical section 116. Once the updated software for the miniOS has been completely written to backup section 114, the UA overwrites the original version of the software for the miniOS in critical section 116 with the updated backup of the software for miniOS (thereby causing critical section 116 to also contain updated software for the miniOS). Assuming that the software for the miniOS has been updated in critical section 116, the boot loader then loads the updated software for the miniOS from critical section 116 to volatile memory and invokes the updated UA (whose software, being part of the miniOS software is now in volatile memory).
The invoked UA (updated or original as described above) then invokes the UPI (updated or original) to update in-place the non-paged core and paged core in sections 118 and 116 respectively (and optionally to update other content in non-volatile memory 110). Once the update has been finished, the UA replaces the update mode flag with the normal mode flag in the designated backup buffer 124. The boot loader then loads the updated software for the non-paged core to volatile memory, invokes the updated non-paged core, and the updated non-paged core starts the normal mode of operation of the updatable device as is known in the art.
What are needed in the art are methods, apparatuses, and memories which avoid storage duplication of procedure(s) which define(s) task(s) that may potentially be required both during the update process and during other unrelated process(es) performed by the updatable device.